package util;

public class IntervalTree {
	private IntervalTree mParent;
	private IntervalTree mLeft;
	private IntervalTree mRight;
	private Interval mData;
	private int mHeight;
	private boolean calcHeight = true;
	private boolean mOccupied = false;
	
	public IntervalTree(){
		this(0, Integer.MAX_VALUE, null);
	}

	public IntervalTree(int start, int end, IntervalTree parent) {
		mData = new Interval(start, end);
		mParent = parent;
	}
	
	private void addInterval(Interval i){
		calcHeight = true;
		mOccupied = true;
		mLeft = new IntervalTree(mData.getStart(), i.getStart(), this);
		mRight = new IntervalTree(i.getEnd(), mData.getEnd(), this);
		mData = new Interval(i.getStart(), i.getEnd());
	}
	
	public Interval getFirstUnoccupied(int start, int duration){	
		Interval res = null;
		if(start < mData.getStart())
			res = mLeft.getFirstUnoccupied(start, duration);
		if(res != null)
			return res;
		start = Math.max(mData.getStart(), start);
		if(!mOccupied){
			if(start+duration <= mData.getEnd() && start >= mData.getStart()){
				res = new Interval(start, start+duration);
				addInterval(res);
				return res;
			}
		} else {
			if(start < mData.getStart())
				res = mLeft.getFirstUnoccupied(start, duration);
			if(res == null)
				res = mRight.getFirstUnoccupied(Math.max(mData.getEnd(), start), duration);
			
		}
		calcHeight = true;
		return res;
	}
	
	public int getHeight(){
		if(calcHeight){
			calcHeight = false;
			if(mLeft == null)
				mHeight = 0;
			else
				mHeight = 1+Math.max(mLeft.getHeight(), mRight.getHeight());
		}
		return mHeight;
	}
	
	public void childBalance(){
		mRight = mRight.balance();
		mLeft = mLeft.balance();
	}
	
	public IntervalTree balance(){
		if(mRight != null && mLeft != null){
			if(mRight.getHeight() - mLeft.getHeight() > 1){
				IntervalTree tmp = mRight.mLeft;
				mRight.mLeft = this;
				mParent = mRight;
				mRight = tmp;
				return mParent;
			} else if(mLeft.getHeight() - mRight.getHeight() > 1){
				IntervalTree tmp = mLeft.mRight;
				mLeft.mRight = this;
				mParent = mLeft;
				mLeft = tmp;
				return mParent;
			}
		}
		return this;
	}
}
